package com.tgy.leetcode.backtracking;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: tgy
 * @Date: 2020-11-21 15:24
 *
 * https://leetcode-cn.com/problems/3sum/
 */
public class _15_三数之和 {

    private int[] nums;

    private List<List<Integer>> lists;

    public List<List<Integer>> threeSum(int[] nums) {


        lists = new LinkedList<>();
        if (nums == null || nums.length == 0) {

            return lists;
        }


        Arrays.sort(nums);

        System.out.println(Arrays.toString(nums));

        this.nums = nums;
        sum(0, 0,new LinkedList<>());

        return lists;
    }


    private void sum(int index, int sum, LinkedList<Integer> candidateList) {

        if (candidateList.size() >= 3) {

            return;
        }


        int tmpSum = 0;
        for (int i = index; i < nums.length; i++) {

            tmpSum = sum + nums[i];

            // 去除同一层相同的
            if (i > index && nums[i - 1] == nums[i]) {

                continue;
            }


            candidateList.add(nums[i]);

            if (tmpSum != 0 || candidateList.size() <= 2) {

                sum(i + 1,tmpSum,candidateList);
            }else  if (tmpSum == 0 && candidateList.size() == 3){

                this.lists.add(new LinkedList<>(candidateList));
            }
            candidateList.removeLast();
        }

    }

}
